package Solution.problem043;

/**
 * @program Leetcode
 * @description:
 * @author: lishangsheng
 * @create: 2019/03/28 18:08
 */
public class Solution {
    /**
     * Multiply Strings 字符串相乘
     * 字符串相乘返回字符串，可以不受int或long的数值范围的约束，我们小时候学习乘法的时候是每位相乘然后错位相加
     * <p>
     * 拆分思路：
     * 1、大数乘以个位数
     * 2、大数相加
     *
     * 把Integer.parseInt 改为 num1.charAt(i)-'0' 时间减少了46ms
     * @param num1
     * @param num2
     * @return
     */
    public static String multiply(String num1, String num2) {


        int length1 = num1.length();
        if(num1.equals("0")){
            return num1;
        }else if(num2.equals("0")){
            return num2;
        }
        String temp = null;
        for (int i = length1 - 1; i >= 0; i--) {
            int numAtI1 = num1.charAt(i)-'0';
            if (temp != null) {
                String tempNum=multiplyNumber(num2, numAtI1);
                temp = sumString(temp,dislocation(tempNum,length1-i));
            } else {
                temp = multiplyNumber(num2, numAtI1);
            }

        }
        return temp;
    }

    private static String dislocation(String num,int length){
        StringBuilder stringBuilder=new StringBuilder();
        stringBuilder.append(num);
        for(;length>1;length--){
            stringBuilder.append(0);
        }
        return stringBuilder.toString();
    }
    private static String multiplyNumber(String num, int single) {
        if (single == 0) {
            return single + "";
        }
        int carr = 0;
        StringBuilder result = new StringBuilder();
        for (int i = num.length() - 1; i >= 0; i--) {
            int numAtI =num.charAt(i)-'0';
            int temp = numAtI * single + carr;
            result.insert(0, temp % 10);
            carr = temp / 10;
        }
        if (carr != 0) {
            result.insert(0, carr);
        }
        return result.toString();
    }

    private static String sumString(String num1, String num2) {
        int len1 = num1.length();
        int len2 = num2.length();
        int carr = 0;
        StringBuilder result = new StringBuilder();
        int i = len1 - 1;
        int j = len2 - 1;
        while (i >= 0 && j >= 0) {
            int numAtI1 = num1.charAt(i) -'0';
            int numAtJ2 = num2.charAt(j)  -'0';
            int temp = numAtI1 + numAtJ2 + carr;
            result.insert(0, (temp) % 10);
            carr = temp / 10;
            i--;
            j--;
        }
        if (i < 0 && j >= 0) {
            for (; j >= 0; j--) {
                int numAtJ2 = num2.charAt(j) -'0';
                int temp = numAtJ2 + carr;
                result.insert(0, (temp) % 10);
                carr = temp / 10;
            }
        } else if (i >= 0) {
            for (; i >= 0; i--) {
                int numAtI1 = num1.charAt(i) -'0';
                int temp = numAtI1 + carr;
                result.insert(0, (temp) % 10);
                carr = temp / 10;
            }
        }
        if (carr != 0) {
            result.insert(0, carr);
        }
        return result.toString();
    }

    public static void main(String[] args) {
        //String test=multiplyNumber("5254",2);
        String test = multiply("9133", "0");
        System.out.println(test);
    }
}
